package com.ma.dp.a01;

import java.util.Arrays;

/**
 * @ClassName Solution174
 * @Author: mayongqiang
 * @DATE 2022/4/12 9:55
 * @Description: 地下城游戏
 */
public class Solution174 {
    public static void main(String[] args) {
        //[[-2,-3,3],[-5,-10,1],[10,30,-5]]  7
        int[][] dungeon = {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};
        System.out.println(calculateMinimumHP02(dungeon));

    }

    /*
    dp[i][j] = x 定义为 从grid[0][0]到grid[i][j]需要的最低生命值为x  信息不足

    修改 dp[i][j] = x 定义为 从grid[i][j]到右下角所需的最低生命值为x
            base case: dp[m-1][n-1] = grid[i][j]>0?1:-grid[i][j]+1;
            target   : dp[0][0]
            state trans:
                从grid[i][j]到右下角所需的最低生命值
                    由从grid[i+1][j]到右下角所需的最低生命值   与  从grid[i][j+1]到右下角所需的最低生命值  决定
                    eg:dp[i+1][j] = 6  dp[i][j+1] = 4  grid[i][j] = 10 / 2 / -2
                    那么选择走i j+1  如果grid[i][j]>=dp[i][j+1]  则dp[i][j] = 1
                                   如果grid[i][j]<dp[i][j+1]  dp[i][j] = 4-2 = 2就够了
                                                                         4+2 = 6
                抽象为方程
                dp[i][j] = f( dp[i+1][j] , dp[i][j+1] )
                        = ( min(dp[i+1][j],dp[i][j+1]) - grid[i][j] ) <=0 ? 1: min(dp[i+1][j],dp[i][j+1]) - grid[i][j]
     */
    static int[][] memo;

    public static int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        memo = new int[m][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        return dp(dungeon, 0, 0);
    }

    private static int dp(int[][] dungeon, int i, int j) {
        int m = dungeon.length;
        int n = dungeon[0].length;

        if (i == m - 1 && j == n - 1) {
            return memo[i][j] = dungeon[i][j] >= 0 ? 1 : -dungeon[i][j] + 1;
        }
        if (i == m || j == n) {
            return Integer.MAX_VALUE;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        int temp = Math.min(dp(dungeon, i + 1, j), dp(dungeon, i, j + 1)) - dungeon[i][j];
        memo[i][j] = temp <= 0 ? 1 : temp;
        return memo[i][j];
    }

    public static int calculateMinimumHP01(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        dp[m - 1][n - 1] = dungeon[m - 1][n - 1] >= 0 ? 1 : -dungeon[m - 1][n - 1] + 1;
        for (int i = m; i >= 0; i--) {
            for (int j = n; j >= 0; j--) {
                if (i == m || j == n) {
                    dp[i][j] = Integer.MAX_VALUE;
                    continue;
                }
                if (i == m - 1 && j == n - 1) {
                    continue;
                }
                int temp = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = temp <= 0 ? 1 : temp;
            }
        }
        return dp[0][0];

    }

    public static int calculateMinimumHP02(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[] dp = new int[n + 1];
        for (int i = m; i >= 0; i--) {
            for (int j = n; j >= 0; j--) {
                if (i == m || j == n) {
                    dp[j] = Integer.MAX_VALUE;
                    continue;
                }
                if (i == m - 1 && j == n - 1) {
                    dp[j] = dungeon[m - 1][n - 1] >= 0 ? 1 : -dungeon[m - 1][n - 1] + 1;
                    continue;
                }
                int temp = Math.min(dp[j], dp[j + 1]) - dungeon[i][j];
                dp[j] = temp <= 0 ? 1 : temp;
            }
        }
        return dp[0];

    }



}
